/**
请你设计一个 贪吃蛇游戏，该游戏将会在一个 屏幕尺寸 = 宽度 x 高度 的屏幕上运行。如果你不熟悉这个游戏，可以 点击这里 在线试玩。

起初时，蛇在左上角的 (0, 0) 位置，身体长度为 1 个单位。

你将会被给出一个 (行, 列) 形式的食物位置序列。当蛇吃到食物时，身子的长度会增加 1 个单位，得分也会 +1。

食物不会同时出现，会按列表的顺序逐一显示在屏幕上。比方讲，第一个食物被蛇吃掉后，第二个食物才会出现。

当一个食物在屏幕上出现时，它被保证不能出现在被蛇身体占据的格子里。

对于每个 move() 操作，你需要返回当前得分或 -1（表示蛇与自己身体或墙相撞，意味游戏结束）。

示例：

给定 width = 3, height = 2, 食物序列为 food = [[1,2],[0,1]]。

Snake snake = new Snake(width, height, food);

初始时，蛇的位置在 (0,0) 且第一个食物在 (1,2)。

|S| | |
| | |F|

snake.move("R"); -> 函数返回 0

| |S| |
| | |F|

snake.move("D"); -> 函数返回 0

| | | |
| |S|F|

snake.move("R"); -> 函数返回 1 (蛇吃掉了第一个食物，同时第二个食物出现在位置 (0,1))

| |F| |
| |S|S|

snake.move("U"); -> 函数返回 1

| |F|S|
| | |S|

snake.move("L"); -> 函数返回 2 (蛇吃掉了第二个食物)

| |S|S|
| | |S|

snake.move("U"); -> 函数返回 -1 (蛇与边界相撞，游戏结束)

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-snake-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
// 化用https://leetcode-cn.com/problems/design-snake-game/solution/c-she-ji-he-li-dai-ma-jian-ji-qing-xi-shi-jian-ji-/ 队列+哈希
type SnakeGame struct {
    M map[int]bool // 记录蛇是否占据了这个位置, 蛇的位置x,y -> x*width+y这一个整数上
    Qf, Qb [][]int // 分别记录蛇和食物的位置
    W, H, Score int
}


/** Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
func Constructor(width int, height int, food [][]int) SnakeGame {
    S :=  SnakeGame{map[int]bool{}, food, [][]int{ } , width, height, 0}
    S.Qb = append(S.Qb, []int{0, 0})
    S.M[0] = true
    return S
}


/** Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body. */
func (this *SnakeGame) Move(direction string) int {

    var IsEnd = func (next []int ) bool{ // 看看是否越界, 或者自己撞上自己
        if this.M[ next[0]*this.W + next[1]] == true || next[0] <0 || next[0]>= this.H || next[1] <0 || next[1] >= this.W {
            return true
        }else{
            return false
        }
    }

    var NewLoc = func( cur []int) []int{ // 获取新的位置
        next := append([]int{}, cur...)
        if( direction == "U"){
            next[0] -= 1
        }
        if( direction == "D"){
            next[0] += 1
        }
        if( direction == "L"){
            next[1] -= 1
        }
        if( direction == "R"){
            next[1] += 1
        }
        
        return next

    }

    var IsFood = func (cur []int) bool{// 是否吃到了食物
        return len(this.Qf) >0 && cur[0]== this.Qf[0][0] && cur[1] ==this.Qf[0][1]
    }

    cur := this.Qb[0]
    next := NewLoc(cur)
    this.M[this.Qb[len(this.Qb)-1][0] * this.W + this.Qb[len(this.Qb)-1][1]] = false // 先移除蛇尾
    if IsEnd(next){ //  结束游戏了
        return -1
    }

   
    this.Qb = append([][]int{next}, this.Qb...) // 蛇头新的位置
    this.M[next[0]*this.W + next[1]] = true // 设置位置为访问过

    if IsFood(next){ // 如果吃到了食物
        this.M[this.Qb[len(this.Qb)-1][0] * this.W + this.Qb[len(this.Qb)-1][1]] = true // 蛇增长的地方就是原来的蛇尾
        this.Qf = this.Qf[1:] // 食物被吃掉了
        this.Score += 1 // 分数增加
        return this.Score
    }

    
    this. Qb = this.Qb[0: len(this.Qb)-1] //  彻底删除原蛇尾的位置

    return this.Score
}


/**
 * Your SnakeGame object will be instantiated and called as such:
 * obj := Constructor(width, height, food);
 * param_1 := obj.Move(direction);
 */
